/**	@file Substitution.cpp
	* @brief Auxiliary functions. */
#include "Substitution.h"
#include "Pow.h"
#include "Mul.h"
#include "Add.h"
#include "Fx.h"
#include "Sym.h"
#include "Number.h"
#include "operators.h"
#include "ComparerIx.h"
namespace sympycpp {
bool Substitution::isAddInAdd(const Add * originalExp, const Add * searchedExp, Sign & sign) {
	const_iterator i, j, last;
	size_t xi, xj, xl;
	xi = xj = xl = 0;//counters
	i = searchedExp->args_.begin();
	last = originalExp->args_.begin();
	j = originalExp->args_.begin();
	const bool COMPARE_SIGN_SYM = false;
	bool findNExt = true;
	bool first = true; // linear search of elements from searchedExp in originalExp
	for (i = searchedExp->args_.begin(); i != searchedExp->args_.end(); ++xi, ++i) {
		if ((*i)->isNum()) {
			continue;
		}	
		for (xj = xl, j = last; (j != originalExp->args_.end()) && (ComparerIx::addLessThan(*j, *i, COMPARE_SIGN_SYM)); ++xj, ++j) {
			if ((searchedExp->args_.size() - xi) > (originalExp->args_.size() - xj)) {
				findNExt = false;
				break;
			}
		} 
		if ((j != originalExp->args_.end()) && !ComparerIx::addLessThan(*i, *j, COMPARE_SIGN_SYM)) {
			last = j;
			xl = xj;
			if (first) {
				first = false;
				sign = (*j)->sign() == (*i)->sign();
			}
			else {
			}
			bool sSigns =  (*j)->sign() == (*i)->sign();
			findNExt = sign ? sSigns: !sSigns;
		}
		else {
			if ((j != originalExp->args_.end()) && (*j)->isMultiple()) {
				if (!ComparerIx::addLessThan(*i, *(++((Mul*)*j)->args_.begin()), COMPARE_SIGN_SYM)) {
					last = j;
					xl = xj;
					if (first) {
						first = false;
						sign = (*j)->sign() == (*i)->sign();
					}
					else {
					}	
					bool sSigns = (*j)->sign() == (*i)->sign();
					findNExt = sign ? sSigns: !sSigns;

				}
				else {
					findNExt = false;
				}
			}
			else {
				findNExt = false;
			}
		}
		if (!findNExt) {
			break;
		}		
	}
	if (xi == searchedExp->args_.size() && findNExt) {
		return true;
	}
	return false;
}

bool Substitution::substituteInAdd(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	Sign sameSign = true;
	Number searchedMultiplicity(1);
	bool ud = false;
	bool isThere = replacedExp->isAdd() ? isAddInAdd((Add *)originalExp, (Add *)replacedExp, sameSign) : false;
	while (isThere && originalExp->isAdd()) {
		ud = true;
		subAddInAdd(originalExp, replacedExp, proxyExp, ratio, sameSign, searchedMultiplicity);
		isThere = (replacedExp->isAdd() && originalExp->isAdd()) ? isAddInAdd((Add *)originalExp, (Add *)replacedExp, sameSign) : false;
	}
	iterator indEx;
	while (originalExp->isAdd() && subInside(((Add *)originalExp)->args_, replacedExp, proxyExp, ratio, indEx)) {
		ud = true;
		Add * origAdd =  (Add *)originalExp;
		Ex * inserter = *indEx;//= origAdd->args_[indEx];
		*indEx = 0;//origAdd->args_[indEx] = 0;
		Ex * temp = 0;
		if ( origAdd->args_.size() == 2) {
			iterator secIndEx = origAdd->args_.begin();//( indEx + 1) % 2;
			if (secIndEx == indEx) {
				++secIndEx;
			}
			temp = *secIndEx;
			*secIndEx = 0;
			delete origAdd;
		}
		else {
			origAdd->omit(indEx);
			temp = originalExp;
		}
		originalExp = Operations::addition( temp, inserter, STEALING);
	}
	return ud || isThere;
}
void Substitution::subAddInAdd(Ex * & originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio, const Sign sameSign, const Number & repalcedMultiplicity) {
	Ex * deleter = replacedExp->copy();
	Ex * inserter = proxyExp->copy();
	Number * Multiplicity = new Number(0);
	Multiplicity->setToMultiplication(*ratio, repalcedMultiplicity);
	MultiplicityMaker(Multiplicity, inserter, STEALING);
	Multiplicity = new Number(repalcedMultiplicity);
	MultiplicityMaker(Multiplicity, deleter, STEALING);
	if (sameSign) {
		deleter->sign(!deleter->sign());
	}
	else {
		inserter->sign(!inserter->sign());
	}
	Ex * temp_e = Operations::addition(originalExp, deleter, STEALING);
	originalExp = Operations::addition(temp_e, inserter, STEALING);
}
bool Substitution::substituteInMultiple(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	Mul * origMul = (Mul *)originalExp;
	iterator first = origMul->args_.begin();
	iterator second = ++origMul->args_.begin();
	Ex * Multiplicity = *first;
	Ex * MultipleExp = *second;
	Multiplicity->sign(originalExp->sign());
	*first = 0;
	*second = 0;
	delete originalExp;
	bool done = false;
	if (replacedExp->isNum()) {
			done = sub2(Multiplicity, replacedExp, proxyExp, ratio);
	}
	done = sub2(MultipleExp, replacedExp, proxyExp, ratio) || done;
	originalExp = Operations::multiplication( Multiplicity, MultipleExp, STEALING);
	return done;
}
bool Substitution::isMulInMul(const Mul * originalExp, const Mul * searchedExp, Sign & sign) {
	size_t xi, xj, xl;
	xi = xj = xl = 0;
	const_iterator i, j, last;
	i = searchedExp->args_.begin();
	j = last = originalExp->args_.begin();
	bool findNExt = true;
	sign = originalExp->sign() == searchedExp->sign();
	for (xi = 0, i = searchedExp->args_.begin(); i != searchedExp->args_.end(); ++xi, ++i) {
		for (xj = xl, j = last; 
		(j != originalExp->args_.end())  && (ComparerIx::auxLessThan(*j, *i));
		 ++xj, ++j)
			if ((searchedExp->args_.size() - xi) > (originalExp->args_.size() - xj)) {
				findNExt = false;
				break;
			}
			if (((j != originalExp->args_.end())) && ((!ComparerIx::auxLessThan(*i, *j)) || 
			   (((*j)->isPow()) && (!ComparerIx::auxLessThan(*i, ((Pow *)*j)->base_))))) {//false
				last = j;
				xl = xj;
			}
			else {
				findNExt = false;
			}
			if (!findNExt) {
				break;
			}
		
		if (!findNExt) {
			break;
		}
	}
	if (xi == searchedExp->args_.size() && findNExt) {
		return true;
	}
	return false;
}
bool Substitution::substituteInMul(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	Sign sameSign = true;
	bool isThere = replacedExp->isMul() ? isMulInMul((Mul *)originalExp, (Mul *)replacedExp, sameSign)  : false ;
	if (isThere) {
		subInMul(originalExp, replacedExp, proxyExp, ratio, sameSign);
	}
	iterator indEx;
	while (originalExp->isMul() && subInside(((Mul *)originalExp)->args_, replacedExp, proxyExp, ratio, indEx)) {
		isThere = true;
		if ((*indEx)->isNum() && (((Number *)(*indEx))->eq(0))) {
			delete originalExp;
			originalExp = new Number(0);
		}
		else {
			if ((*indEx)->isNum() && (((Number *)(*indEx))->eq(1))) {
				Mul * origMul = (Mul *)originalExp;
				if (origMul->args_.size() == 2) {
					iterator res = origMul->args_.begin();
					if (res == indEx) {
						++res;
					}
					originalExp = *res;
					originalExp->sign(origMul->sign() == originalExp->sign());
					(*res) = 0;
					delete origMul;
				}
				else {
					origMul->omit(indEx);
				}

			}
			else {
				Mul * origMul = (Mul *)originalExp;
				Ex * inserter = *indEx;//origMul->args_[indEx]; 
				*indEx = 0;//origMul->args_[indEx] = 0;
				Ex * temp = 0;
				if (origMul->args_.size() == 2) {
					//size_t secIndEx = (indEx + 1) % 2;
					iterator secIndEx = origMul->args_.begin();
					if (secIndEx == indEx) {
						++secIndEx;
					}
					temp = *secIndEx;//origMul->args_[secIndEx];
					(*secIndEx) = 0; // origMul->args_[secIndEx] = 0;
					temp->sign(origMul->sign());
					delete origMul;
				}
				else {
					origMul->omit(indEx);
					temp = originalExp;
				}
				originalExp = Operations::multiplication( temp, inserter, STEALING);
			}
		}
	}
	return isThere;
}
void Substitution::subInMul(Ex * & originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio, const Sign sameSign) {
	Ex * auxDeleter = replacedExp->copy();
	Ex * MultiplicityOfInserter = ratio->copy();
	Ex * auxInserter = proxyExp->copy();
	Ex * minusOne = new Number(-1);

	Ex * deleter = Operations::power(auxDeleter, minusOne, STEALING);
	Ex * inserter = Operations::multiplication(auxInserter, MultiplicityOfInserter, STEALING);

	Ex * temp = Operations::multiplication(originalExp, deleter, STEALING);
	originalExp = Operations::multiplication(temp, inserter, STEALING);
}
bool Substitution::substituteInNum(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	if (replacedExp->isNum()) {
		Number *  replacedVal = (Number *)replacedExp;
		if (replacedVal->eq(0)) {
			return false;
		}
		Number * originalVal = (Number *)originalExp;
		Number * ratioVal = (Number *)ratio;
//		Num divVal = originalVal / replacedVal;
		Number divVal(0);
		divVal.setToDivision(*originalVal, *replacedVal);
		//Num newVal = originalVal - divVal*replacedVal;
		Number * newVal = new Number(0);
		newVal->setToMultiplication(divVal, *replacedVal);
		newVal->setToSubtraction(*originalVal, *newVal);
		delete originalExp;
//		Number * newRatio = new Number(divVal * ratioVal);
		Number * newRatio = new Number(0);
		newRatio->setToMultiplication(divVal, *ratioVal);		
		Ex * proxy = proxyExp->copy();
		MultiplicityMaker(newRatio, proxy, STEALING);
		Ex * number = newVal;
		originalExp = Operations::addition(number, proxy, STEALING);
		return true; 
	}
	return false;
}
bool Substitution::substituteInSym(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	if (replacedExp->isSym()) {
		if (ComparerIx::unsignedTextCompare(originalExp, replacedExp)) {
			Sign newSign = originalExp->sign() == replacedExp->sign() ? proxyExp->sign() : !proxyExp->sign();
			delete originalExp;
			Number * newRatio = (Number *)ratio->copy();
			Ex * proxy = proxyExp->copy();
			proxy->sign(newSign);
			MultiplicityMaker(newRatio, proxy, STEALING);
			originalExp = proxy;
			return true;
		}
	}
	return false;
}
bool Substitution::substituteInPow(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	Pow * origPow = (Pow *)originalExp;
	Ex * exp = origPow->exponent_;
	Ex * base = origPow->base_;
	if (sub2(exp, replacedExp, proxyExp, ratio) || sub2(base, replacedExp, proxyExp, ratio)) {
		origPow->exponent_ = 0;
		origPow->base_ = 0;
		Sign s = originalExp->sign();
		delete originalExp;
		originalExp = Operations::power(base, exp, STEALING);
		originalExp->sign(s == originalExp->sign());
		return true;	
	}
	else {
		if (replacedExp->isPow()) {
			const Pow * repPow = (Pow *)replacedExp;
			if (repPow->base_->unsigned_str() == base->unsigned_str()) {
				Ex * divisor = repPow->exponent_->copy();
				((Pow *)originalExp)->exponent_ = 0; // ..exponent_ & exp are pointing on the same place
				Ex * newExp = Operations::division(exp, divisor, STEALING);
				Ex * newBase = proxyExp->copy();
				Number * multiplicity = (Number *)ratio->copy();
				MultiplicityMaker(multiplicity, newBase, STEALING);
				if (repPow->base_->sign() != origPow->base_->sign()) {
					Ex * cpExp = repPow->exponent_->copy();
					Ex * minOne = new Number(-1);
					Ex * prefix = Operations::power(minOne, cpExp, STEALING);
					newBase = Operations::multiplication(prefix, newBase, STEALING);
				}
				Ex * newExpr =  Operations::power(newBase, newExp, STEALING);
				newExpr->sign(originalExp->sign());
				delete originalExp;
				originalExp = newExpr;
				return true;
			}
		}
		return false;
	}
}

bool Substitution::substituteInFx(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	if (ComparerIx::unsignedTextCompare(originalExp, replacedExp)) {
		Ex * newEx = proxyExp->copy();
		newEx->sign( originalExp->sign() == replacedExp->sign());
		delete originalExp;
		originalExp = newEx;
		return true;
	}
	else {
		if (sub2(((Fx *)originalExp)->e_, replacedExp, proxyExp, ratio)) {
			Fx * f = (Fx *)originalExp;
			Ex * arg = f->e_;
			f->e_ = 0;
			originalExp = f->create(arg, STEALING);
			originalExp->sign(f->sign() == originalExp->sign() ? plus : minus);
			delete f;
			return true;
		}
		else {
			return false;
		}
	}
}
void Substitution::sub(Ex * & originalEx, const Ex * fromEx, const Ex * toEx) {
	if (fromEx->isNum()) {
		return ;
	}
	Number * ratio = new Number(1);
	const Ex * cto = toEx;
	const Ex * cfrom = fromEx;
	if (toEx->isMultiple()) {
		iterator first = ((Mul *)toEx)->args_.begin();
		iterator second = ((Mul *)toEx)->args_.begin();
		++second;
		cto = *second;//((Mul *)toEx)->args_[1];
		ratio->setValue(*((Number *)*first));//((Mul *)toEx)->args_[0]));
		ratio->sign(toEx->sign());
	}
	if (fromEx->isMultiple()) {
			iterator first = ((Mul *)fromEx)->args_.begin();
			iterator second = ((Mul *)fromEx)->args_.begin();
			++second;
			cfrom = *second;//((Mul *)fromEx)->args_[1];
			//ratio->setValue(ratio->getValue() / ((Number *)((Mul *)fromEx)->args_[0])->getValue());
			ratio->setToDivision(*ratio, *((Number *)*first));//((Mul *)fromEx)->args_[0]));
			ratio->sign(ratio->sign() == fromEx->sign() ? plus : minus);
	}

//	bool changed =  from->isMultiple() || from->isPow();
//	while (changed) {
//		changed = false;
		if (cfrom->isPow()) {
			Ex * fr = cfrom->copy();
			Ex * to = cto->copy();
			Ex * from = ((Pow *)fr)->base_;
			((Pow *)fr)->base_ = 0;
	
			Sign signChange = fr->sign() ? to->sign() : !to->sign();
			to->sign(signChange);
	
			Ex * minOne = new Number(-1);
			
			Ex * exponent = ((Pow *)fr)->exponent_;
			((Pow*)fr)->exponent_ = 0;
	
			Ex * invertedExp = Operations::power(exponent, minOne, STEALING);
			Ex * tratio = ratio;	
			Ex * temp = Operations::multiplication(to, tratio, STEALING);
			to = Operations::power(temp, invertedExp, STEALING);
			sub(originalEx, from, to);
			delete fr;
			delete from;
			delete to;
			return ;

		}
	while (sub2(originalEx, cfrom, cto, ratio));// std::cout << "REKUR >>  " << originalEx->str() << std::endl;
	delete ratio;
}
bool Substitution::sub2(Ex * &  originalExp, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio) {
	if (originalExp->rsize() < replacedExp->rsize()) {
		return false;
	}
	if (ComparerIx::unsignedTextCompare(originalExp, replacedExp)) {
		Sign chSign = !(originalExp->sign() == replacedExp->sign() ? plus : minus);
		delete originalExp;
		Number * newRatio = (Number *)ratio->copy();
		Ex * proxy = proxyExp->copy();
		MultiplicityMaker(newRatio, proxy, STEALING);
		originalExp = proxy;
		if (chSign) {
			originalExp->sign(!originalExp->sign());
		}
		return true;
	}
	
	if (originalExp->isAdd()) {
		return  substituteInAdd(originalExp, replacedExp, proxyExp, ratio);
	}
	if (originalExp->isMultiple()) {
		bool p =  substituteInMultiple(originalExp, replacedExp, proxyExp, ratio);
		return p;
	}
	if (originalExp->isMul()) {
		bool p =  substituteInMul(originalExp, replacedExp, proxyExp, ratio);
		return p;
	}
	if (originalExp->isNum()) {
		return substituteInNum(originalExp, replacedExp, proxyExp, ratio);
	}
	if (originalExp->isSym()) {
		return substituteInSym(originalExp, replacedExp, proxyExp, ratio);
	}
	if (originalExp->isPow()) {
		return substituteInPow(originalExp, replacedExp, proxyExp, ratio);
	}
	if (originalExp->isFx()) {
		return substituteInFx(originalExp, replacedExp, proxyExp, ratio);
	}	
	return false;	
}
bool Substitution::subInside(basic_container &  Exs, const Ex * replacedExp,const Ex * proxyExp, const Number * ratio, iterator & indEx) {
	for(iterator i = Exs.begin(); i != Exs.end(); ++i) {
		if ( sub2(*i, replacedExp, proxyExp, ratio)) {
			indEx = i;
			return true; 
		}	
	}
	return false;
}
void Substitution::MultiplicityMaker(Number * & ratio, Ex * & Expression, const allocationPolicy policy) {
	if (!ratio->eq(1)) {
		Ex * newMul = Operations::multiplication((Ex * &)ratio, Expression, STEALING);
		ratio = 0;
		Expression = newMul;
	}
	else {
		delete ratio;
		ratio = 0;
	}
}
}
